package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.Comparator;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC435 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int eraseOverlapIntervals(int[][] intervals) {
            Arrays.sort(intervals, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });

            int nonOverlapCount = 0, lastIntervalRightBorder = Integer.MIN_VALUE;
            for (int[] interval : intervals) {
                if (interval[0] >= lastIntervalRightBorder) {
                    ++nonOverlapCount;
                    lastIntervalRightBorder = interval[1];
                }
            }

            return intervals.length - nonOverlapCount;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = InputUtil.toDoubleIntegerArray("[\n" +
                "    [\n" +
                "        -100,\n" +
                "        -87\n" +
                "    ],\n" +
                "    [\n" +
                "        -99,\n" +
                "        -44\n" +
                "    ],\n" +
                "    [\n" +
                "        -98,\n" +
                "        -19\n" +
                "    ],\n" +
                "    [\n" +
                "        -97,\n" +
                "        -33\n" +
                "    ],\n" +
                "    [\n" +
                "        -96,\n" +
                "        -60\n" +
                "    ],\n" +
                "    [\n" +
                "        -95,\n" +
                "        -17\n" +
                "    ],\n" +
                "    [\n" +
                "        -94,\n" +
                "        -44\n" +
                "    ],\n" +
                "    [\n" +
                "        -93,\n" +
                "        -9\n" +
                "    ],\n" +
                "    [\n" +
                "        -92,\n" +
                "        -63\n" +
                "    ],\n" +
                "    [\n" +
                "        -91,\n" +
                "        -76\n" +
                "    ],\n" +
                "    [\n" +
                "        -90,\n" +
                "        -44\n" +
                "    ],\n" +
                "    [\n" +
                "        -89,\n" +
                "        -18\n" +
                "    ],\n" +
                "    [\n" +
                "        -88,\n" +
                "        10\n" +
                "    ],\n" +
                "    [\n" +
                "        -87,\n" +
                "        -39\n" +
                "    ],\n" +
                "    [\n" +
                "        -86,\n" +
                "        7\n" +
                "    ],\n" +
                "    [\n" +
                "        -85,\n" +
                "        -76\n" +
                "    ],\n" +
                "    [\n" +
                "        -84,\n" +
                "        -51\n" +
                "    ],\n" +
                "    [\n" +
                "        -83,\n" +
                "        -48\n" +
                "    ],\n" +
                "    [\n" +
                "        -82,\n" +
                "        -36\n" +
                "    ],\n" +
                "    [\n" +
                "        -81,\n" +
                "        -63\n" +
                "    ],\n" +
                "    [\n" +
                "        -80,\n" +
                "        -71\n" +
                "    ],\n" +
                "    [\n" +
                "        -79,\n" +
                "        -4\n" +
                "    ],\n" +
                "    [\n" +
                "        -78,\n" +
                "        -63\n" +
                "    ],\n" +
                "    [\n" +
                "        -77,\n" +
                "        -14\n" +
                "    ],\n" +
                "    [\n" +
                "        -76,\n" +
                "        -10\n" +
                "    ],\n" +
                "    [\n" +
                "        -75,\n" +
                "        -36\n" +
                "    ],\n" +
                "    [\n" +
                "        -74,\n" +
                "        31\n" +
                "    ],\n" +
                "    [\n" +
                "        -73,\n" +
                "        11\n" +
                "    ],\n" +
                "    [\n" +
                "        -72,\n" +
                "        -50\n" +
                "    ],\n" +
                "    [\n" +
                "        -71,\n" +
                "        -30\n" +
                "    ],\n" +
                "    [\n" +
                "        -70,\n" +
                "        33\n" +
                "    ],\n" +
                "    [\n" +
                "        -69,\n" +
                "        -37\n" +
                "    ],\n" +
                "    [\n" +
                "        -68,\n" +
                "        -50\n" +
                "    ],\n" +
                "    [\n" +
                "        -67,\n" +
                "        6\n" +
                "    ],\n" +
                "    [\n" +
                "        -66,\n" +
                "        -50\n" +
                "    ],\n" +
                "    [\n" +
                "        -65,\n" +
                "        -26\n" +
                "    ],\n" +
                "    [\n" +
                "        -64,\n" +
                "        21\n" +
                "    ],\n" +
                "    [\n" +
                "        -63,\n" +
                "        -8\n" +
                "    ],\n" +
                "    [\n" +
                "        -62,\n" +
                "        23\n" +
                "    ],\n" +
                "    [\n" +
                "        -61,\n" +
                "        -34\n" +
                "    ],\n" +
                "    [\n" +
                "        -60,\n" +
                "        13\n" +
                "    ],\n" +
                "    [\n" +
                "        -59,\n" +
                "        19\n" +
                "    ],\n" +
                "    [\n" +
                "        -58,\n" +
                "        41\n" +
                "    ],\n" +
                "    [\n" +
                "        -57,\n" +
                "        -15\n" +
                "    ],\n" +
                "    [\n" +
                "        -56,\n" +
                "        35\n" +
                "    ],\n" +
                "    [\n" +
                "        -55,\n" +
                "        -4\n" +
                "    ],\n" +
                "    [\n" +
                "        -54,\n" +
                "        -20\n" +
                "    ],\n" +
                "    [\n" +
                "        -53,\n" +
                "        44\n" +
                "    ],\n" +
                "    [\n" +
                "        -52,\n" +
                "        48\n" +
                "    ],\n" +
                "    [\n" +
                "        -51,\n" +
                "        12\n" +
                "    ],\n" +
                "    [\n" +
                "        -50,\n" +
                "        -43\n" +
                "    ],\n" +
                "    [\n" +
                "        -49,\n" +
                "        10\n" +
                "    ],\n" +
                "    [\n" +
                "        -48,\n" +
                "        -34\n" +
                "    ],\n" +
                "    [\n" +
                "        -47,\n" +
                "        3\n" +
                "    ],\n" +
                "    [\n" +
                "        -46,\n" +
                "        28\n" +
                "    ],\n" +
                "    [\n" +
                "        -45,\n" +
                "        51\n" +
                "    ],\n" +
                "    [\n" +
                "        -44,\n" +
                "        -14\n" +
                "    ],\n" +
                "    [\n" +
                "        -43,\n" +
                "        59\n" +
                "    ],\n" +
                "    [\n" +
                "        -42,\n" +
                "        -6\n" +
                "    ],\n" +
                "    [\n" +
                "        -41,\n" +
                "        -32\n" +
                "    ],\n" +
                "    [\n" +
                "        -40,\n" +
                "        -12\n" +
                "    ],\n" +
                "    [\n" +
                "        -39,\n" +
                "        33\n" +
                "    ],\n" +
                "    [\n" +
                "        -38,\n" +
                "        17\n" +
                "    ],\n" +
                "    [\n" +
                "        -37,\n" +
                "        -7\n" +
                "    ],\n" +
                "    [\n" +
                "        -36,\n" +
                "        -29\n" +
                "    ],\n" +
                "    [\n" +
                "        -35,\n" +
                "        24\n" +
                "    ],\n" +
                "    [\n" +
                "        -34,\n" +
                "        49\n" +
                "    ],\n" +
                "    [\n" +
                "        -33,\n" +
                "        -19\n" +
                "    ],\n" +
                "    [\n" +
                "        -32,\n" +
                "        2\n" +
                "    ],\n" +
                "    [\n" +
                "        -31,\n" +
                "        8\n" +
                "    ],\n" +
                "    [\n" +
                "        -30,\n" +
                "        74\n" +
                "    ],\n" +
                "    [\n" +
                "        -29,\n" +
                "        58\n" +
                "    ],\n" +
                "    [\n" +
                "        -28,\n" +
                "        13\n" +
                "    ],\n" +
                "    [\n" +
                "        -27,\n" +
                "        -8\n" +
                "    ],\n" +
                "    [\n" +
                "        -26,\n" +
                "        45\n" +
                "    ],\n" +
                "    [\n" +
                "        -25,\n" +
                "        -5\n" +
                "    ],\n" +
                "    [\n" +
                "        -24,\n" +
                "        45\n" +
                "    ],\n" +
                "    [\n" +
                "        -23,\n" +
                "        19\n" +
                "    ],\n" +
                "    [\n" +
                "        -22,\n" +
                "        9\n" +
                "    ],\n" +
                "    [\n" +
                "        -21,\n" +
                "        54\n" +
                "    ],\n" +
                "    [\n" +
                "        -20,\n" +
                "        1\n" +
                "    ],\n" +
                "    [\n" +
                "        -19,\n" +
                "        81\n" +
                "    ],\n" +
                "    [\n" +
                "        -18,\n" +
                "        17\n" +
                "    ],\n" +
                "    [\n" +
                "        -17,\n" +
                "        -10\n" +
                "    ],\n" +
                "    [\n" +
                "        -16,\n" +
                "        7\n" +
                "    ],\n" +
                "    [\n" +
                "        -15,\n" +
                "        86\n" +
                "    ],\n" +
                "    [\n" +
                "        -14,\n" +
                "        -3\n" +
                "    ],\n" +
                "    [\n" +
                "        -13,\n" +
                "        -3\n" +
                "    ],\n" +
                "    [\n" +
                "        -12,\n" +
                "        45\n" +
                "    ],\n" +
                "    [\n" +
                "        -11,\n" +
                "        93\n" +
                "    ],\n" +
                "    [\n" +
                "        -10,\n" +
                "        84\n" +
                "    ],\n" +
                "    [\n" +
                "        -9,\n" +
                "        20\n" +
                "    ],\n" +
                "    [\n" +
                "        -8,\n" +
                "        3\n" +
                "    ],\n" +
                "    [\n" +
                "        -7,\n" +
                "        81\n" +
                "    ],\n" +
                "    [\n" +
                "        -6,\n" +
                "        52\n" +
                "    ],\n" +
                "    [\n" +
                "        -5,\n" +
                "        67\n" +
                "    ],\n" +
                "    [\n" +
                "        -4,\n" +
                "        18\n" +
                "    ],\n" +
                "    [\n" +
                "        -3,\n" +
                "        40\n" +
                "    ],\n" +
                "    [\n" +
                "        -2,\n" +
                "        42\n" +
                "    ],\n" +
                "    [\n" +
                "        -1,\n" +
                "        49\n" +
                "    ],\n" +
                "    [\n" +
                "        0,\n" +
                "        7\n" +
                "    ],\n" +
                "    [\n" +
                "        1,\n" +
                "        104\n" +
                "    ],\n" +
                "    [\n" +
                "        2,\n" +
                "        79\n" +
                "    ],\n" +
                "    [\n" +
                "        3,\n" +
                "        37\n" +
                "    ],\n" +
                "    [\n" +
                "        4,\n" +
                "        47\n" +
                "    ],\n" +
                "    [\n" +
                "        5,\n" +
                "        69\n" +
                "    ],\n" +
                "    [\n" +
                "        6,\n" +
                "        89\n" +
                "    ],\n" +
                "    [\n" +
                "        7,\n" +
                "        110\n" +
                "    ],\n" +
                "    [\n" +
                "        8,\n" +
                "        108\n" +
                "    ],\n" +
                "    [\n" +
                "        9,\n" +
                "        19\n" +
                "    ],\n" +
                "    [\n" +
                "        10,\n" +
                "        25\n" +
                "    ],\n" +
                "    [\n" +
                "        11,\n" +
                "        48\n" +
                "    ],\n" +
                "    [\n" +
                "        12,\n" +
                "        63\n" +
                "    ],\n" +
                "    [\n" +
                "        13,\n" +
                "        94\n" +
                "    ],\n" +
                "    [\n" +
                "        14,\n" +
                "        55\n" +
                "    ],\n" +
                "    [\n" +
                "        15,\n" +
                "        119\n" +
                "    ],\n" +
                "    [\n" +
                "        16,\n" +
                "        64\n" +
                "    ],\n" +
                "    [\n" +
                "        17,\n" +
                "        122\n" +
                "    ],\n" +
                "    [\n" +
                "        18,\n" +
                "        92\n" +
                "    ],\n" +
                "    [\n" +
                "        19,\n" +
                "        37\n" +
                "    ],\n" +
                "    [\n" +
                "        20,\n" +
                "        86\n" +
                "    ],\n" +
                "    [\n" +
                "        21,\n" +
                "        84\n" +
                "    ],\n" +
                "    [\n" +
                "        22,\n" +
                "        122\n" +
                "    ],\n" +
                "    [\n" +
                "        23,\n" +
                "        37\n" +
                "    ],\n" +
                "    [\n" +
                "        24,\n" +
                "        125\n" +
                "    ],\n" +
                "    [\n" +
                "        25,\n" +
                "        99\n" +
                "    ],\n" +
                "    [\n" +
                "        26,\n" +
                "        45\n" +
                "    ],\n" +
                "    [\n" +
                "        27,\n" +
                "        63\n" +
                "    ],\n" +
                "    [\n" +
                "        28,\n" +
                "        40\n" +
                "    ],\n" +
                "    [\n" +
                "        29,\n" +
                "        97\n" +
                "    ],\n" +
                "    [\n" +
                "        30,\n" +
                "        78\n" +
                "    ],\n" +
                "    [\n" +
                "        31,\n" +
                "        102\n" +
                "    ],\n" +
                "    [\n" +
                "        32,\n" +
                "        120\n" +
                "    ],\n" +
                "    [\n" +
                "        33,\n" +
                "        91\n" +
                "    ],\n" +
                "    [\n" +
                "        34,\n" +
                "        107\n" +
                "    ],\n" +
                "    [\n" +
                "        35,\n" +
                "        62\n" +
                "    ],\n" +
                "    [\n" +
                "        36,\n" +
                "        137\n" +
                "    ],\n" +
                "    [\n" +
                "        37,\n" +
                "        55\n" +
                "    ],\n" +
                "    [\n" +
                "        38,\n" +
                "        115\n" +
                "    ],\n" +
                "    [\n" +
                "        39,\n" +
                "        46\n" +
                "    ],\n" +
                "    [\n" +
                "        40,\n" +
                "        136\n" +
                "    ],\n" +
                "    [\n" +
                "        41,\n" +
                "        78\n" +
                "    ],\n" +
                "    [\n" +
                "        42,\n" +
                "        86\n" +
                "    ],\n" +
                "    [\n" +
                "        43,\n" +
                "        106\n" +
                "    ],\n" +
                "    [\n" +
                "        44,\n" +
                "        66\n" +
                "    ],\n" +
                "    [\n" +
                "        45,\n" +
                "        141\n" +
                "    ],\n" +
                "    [\n" +
                "        46,\n" +
                "        92\n" +
                "    ],\n" +
                "    [\n" +
                "        47,\n" +
                "        132\n" +
                "    ],\n" +
                "    [\n" +
                "        48,\n" +
                "        89\n" +
                "    ],\n" +
                "    [\n" +
                "        49,\n" +
                "        61\n" +
                "    ],\n" +
                "    [\n" +
                "        50,\n" +
                "        128\n" +
                "    ],\n" +
                "    [\n" +
                "        51,\n" +
                "        155\n" +
                "    ],\n" +
                "    [\n" +
                "        52,\n" +
                "        153\n" +
                "    ],\n" +
                "    [\n" +
                "        53,\n" +
                "        78\n" +
                "    ],\n" +
                "    [\n" +
                "        54,\n" +
                "        114\n" +
                "    ],\n" +
                "    [\n" +
                "        55,\n" +
                "        84\n" +
                "    ],\n" +
                "    [\n" +
                "        56,\n" +
                "        151\n" +
                "    ],\n" +
                "    [\n" +
                "        57,\n" +
                "        123\n" +
                "    ],\n" +
                "    [\n" +
                "        58,\n" +
                "        69\n" +
                "    ],\n" +
                "    [\n" +
                "        59,\n" +
                "        91\n" +
                "    ],\n" +
                "    [\n" +
                "        60,\n" +
                "        89\n" +
                "    ],\n" +
                "    [\n" +
                "        61,\n" +
                "        73\n" +
                "    ],\n" +
                "    [\n" +
                "        62,\n" +
                "        81\n" +
                "    ],\n" +
                "    [\n" +
                "        63,\n" +
                "        139\n" +
                "    ],\n" +
                "    [\n" +
                "        64,\n" +
                "        108\n" +
                "    ],\n" +
                "    [\n" +
                "        65,\n" +
                "        165\n" +
                "    ],\n" +
                "    [\n" +
                "        66,\n" +
                "        92\n" +
                "    ],\n" +
                "    [\n" +
                "        67,\n" +
                "        117\n" +
                "    ],\n" +
                "    [\n" +
                "        68,\n" +
                "        140\n" +
                "    ],\n" +
                "    [\n" +
                "        69,\n" +
                "        109\n" +
                "    ],\n" +
                "    [\n" +
                "        70,\n" +
                "        102\n" +
                "    ],\n" +
                "    [\n" +
                "        71,\n" +
                "        171\n" +
                "    ],\n" +
                "    [\n" +
                "        72,\n" +
                "        141\n" +
                "    ],\n" +
                "    [\n" +
                "        73,\n" +
                "        117\n" +
                "    ],\n" +
                "    [\n" +
                "        74,\n" +
                "        124\n" +
                "    ],\n" +
                "    [\n" +
                "        75,\n" +
                "        171\n" +
                "    ],\n" +
                "    [\n" +
                "        76,\n" +
                "        132\n" +
                "    ],\n" +
                "    [\n" +
                "        77,\n" +
                "        142\n" +
                "    ],\n" +
                "    [\n" +
                "        78,\n" +
                "        107\n" +
                "    ],\n" +
                "    [\n" +
                "        79,\n" +
                "        132\n" +
                "    ],\n" +
                "    [\n" +
                "        80,\n" +
                "        171\n" +
                "    ],\n" +
                "    [\n" +
                "        81,\n" +
                "        104\n" +
                "    ],\n" +
                "    [\n" +
                "        82,\n" +
                "        160\n" +
                "    ],\n" +
                "    [\n" +
                "        83,\n" +
                "        128\n" +
                "    ],\n" +
                "    [\n" +
                "        84,\n" +
                "        137\n" +
                "    ],\n" +
                "    [\n" +
                "        85,\n" +
                "        176\n" +
                "    ],\n" +
                "    [\n" +
                "        86,\n" +
                "        188\n" +
                "    ],\n" +
                "    [\n" +
                "        87,\n" +
                "        178\n" +
                "    ],\n" +
                "    [\n" +
                "        88,\n" +
                "        117\n" +
                "    ],\n" +
                "    [\n" +
                "        89,\n" +
                "        115\n" +
                "    ],\n" +
                "    [\n" +
                "        90,\n" +
                "        140\n" +
                "    ],\n" +
                "    [\n" +
                "        91,\n" +
                "        165\n" +
                "    ],\n" +
                "    [\n" +
                "        92,\n" +
                "        133\n" +
                "    ],\n" +
                "    [\n" +
                "        93,\n" +
                "        114\n" +
                "    ],\n" +
                "    [\n" +
                "        94,\n" +
                "        125\n" +
                "    ],\n" +
                "    [\n" +
                "        95,\n" +
                "        135\n" +
                "    ],\n" +
                "    [\n" +
                "        96,\n" +
                "        144\n" +
                "    ],\n" +
                "    [\n" +
                "        97,\n" +
                "        114\n" +
                "    ],\n" +
                "    [\n" +
                "        98,\n" +
                "        183\n" +
                "    ],\n" +
                "    [\n" +
                "        99,\n" +
                "        157\n" +
                "    ]\n" +
                "]");
        System.out.println(solution.eraseOverlapIntervals(arr));
    }

    public static void main(String[] args) throws Exception {
        LC435 an = new LC435();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
